package likou;

import java.util.Arrays;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/11 13:15
 */
public class _279 {
    public static void main(String[] args) {
        System.out.println(numSquares2(43));
    }

    public static int numSquares2(int n) {
        int[] nums = new int[n + 1];
        Arrays.fill(nums, Integer.MAX_VALUE);
        nums[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                nums[i] = Math.min(nums[i - j * j] + 1, nums[i]);
            }
            System.out.println(Arrays.toString(nums));
        }
        return nums[n];
    }

    public static int numSquares(int n) {
        int res = Integer.MAX_VALUE;
        for (int deep = 1; deep * deep <= n; deep++) {
            int now = n;
            if (deep * deep == now) {
                return 1;
            }
            int dp = deep;
            int nowRes = 0;
            //43-9=34,34=25+9
            while (now > 0) {
                System.out.println(now / (dp * dp) + "个" + dp * dp);
                if (now/ (dp * dp)>0){
                    nowRes += now / (dp * dp);
                    now %= (dp * dp);
                }
                dp--;
            }
            System.out.println("--------" + nowRes + "--------");
            res = Math.min(res, nowRes);
        }
        return res;
    }
}
